package LeetCode_343;

/**
 * @author : niu niu
 * @version : 1.0.0
 * @date : 2023/4/7 19:44
 */
public class Solution {
    //-----------math
    // 4 = 2 2   5 = 2 3    6 = 3 2   7 = 4 3 = 2 2 3  8 = 4 2 = 2 2 2  9 = 3 3  .。。。。
    public int integerBreak(int n) {
        if (n<=3 ){
            return n-1;
        }
        int div = n/3;
        int mod = n%3;
        if (mod ==1){
            return (int)Math.pow(3,div-1)*4;
        }else if (mod ==2 ){
            return (int) Math.pow(3,div)*2;
        }else {
            return (int) Math.pow(3,div);
        }
    }

    //-------------dp

    public int integerBreakDp(int n) {
        int[] dp =new int[n+1];
        dp[0] = dp[1]    = 0;
        for (int i = 2; i < n+1; i++) {
            int cur = 0;
            for (int j = 1; j < i; j++) {
                cur  = Math.max(cur,Math.max(j*(i-j),j*dp[i-j]));
            }
            dp[i]=cur;
        }
        return dp[n];
    }
}
